package linear

import (
	"gitee.com/jinyunliu/algorithm/util"
	"math"
)

// MergeTwoSortedArr 合并两个有序的数组
// 面临的问题就是不等长数组 但是有序, 可以填入指定的切片, 注意尽可能把 代码的逻辑 布局写的相对美观一些, 有一些面试官 就是看代码风格的;
// 不要写的乱糟糟的, 尽管我们可以通过 接口 抽象行为;
// 下面这个实现确实有点乱 重新写一下
func MergeTwoSortedArr(num1 []int, num2 []int) []int {
	r, ri, i, j := make([]int, len(num2)+len(num1)), 0, 0, 0

	// 两个有序数组进行merge: pre-condition: sorted
	for ; i < len(num1) && j < len(num2); ri++ {
		if num1[i] <= num2[j] {
			r[ri] = num1[i]
			i++
		} else {
			r[ri] = num2[j]
			j++
		}
	}

	for ; i < len(num1); i++ {
		r[ri] = num1[i]
		ri++
	}

	for ; j < len(num2); j++ {
		r[ri] = num2[j]
		ri++
	}

	return r
}

// 超级水王数 场景: 比如一个帖子 如果有一半以上都是一个人回复的 这就是水军 出现次数大于一半以上
// 一个数组中 查找出出现次数大于一半的数  raft 协议选举就是通过这个选票 推选出leader的;
// 选举问题 只有得到大于一半票数的才能获胜
// 有限几个变量 o(1) o(n) 有限次遍历

// FindMaxWater 在一个数组中出现次数大于等于一半
func FindMaxWater(arr []int) int {
	// 是否有候选人 可以用票来标识 至少存在一票标识有候选
	candidate, votes := -1, 0
	for i := 0; i < len(arr); i++ {
		if votes == 0 {
			// 没有候选人
			candidate = i
			votes++
		} else if arr[i] == arr[candidate] {
			votes++
		} else {
			votes--
		}
	}

	if votes == 0 {
		return -1
	}

	votes = 0
	for i := 0; i < len(arr); i++ {
		if arr[candidate] == arr[i] {
			votes++
		}
	}

	// > 1/2 奇数= 奇数-1/2 相同
	if votes >= len(arr)>>1 {
		return candidate
	}

	return -1
}

// TwoSum 两数之和 本题是在一个没有重复的数组中查找两个数索引返回
// 不重复查找 使用一个等长的hash table效率高
// leetcode1
func TwoSum(nums []int, target int) []int {
	hash := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		// 如果 target - nums[i] 在hash表中查找不到 就把这个数也放到hash表中
		if pi, ok := hash[target-nums[i]]; ok {
			return []int{pi, i}
		} else {
			hash[nums[i]] = i
		}
	}

	return nil
}

// FindMedianSortedArrays 寻找两个有序数组的中位数  使用分割线;
// leetcode4 寻找两个有序数组的中位数
// 中位数定义： 有序数组 如果长度是奇数 n/2 就是中位数 如果是偶数 (n/2 + n/2-1) >> 1 就是中位数
func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var (
		m            = len(nums1)
		n            = len(nums2)
		l            = (m + n + 1) >> 1
		left         = 0
		right        = m
		maxLeftNums1 = math.MinInt32
		maxLeftNums2 = math.MinInt32

		minRightNums1 = math.MaxInt32
		minRightNums2 = math.MaxInt32
	)

	if m > n {
		return FindMedianSortedArrays(nums2, nums1)
	}

	// len(left) = (m + n + 1) >>1    separator line;
	// if 第一个左边i, 分割线左边就是i;  那么第二个数组 左边 就是 len(left) - i 个 分割线右边就是j
	// 处理查找边界问题; i = 0; j = 0; i=m; j=n 这些问题, 直接取无穷+

	// 对num1 进行Binary Search 边界search 不能相等 不然就没有值    i∈[0, m]
	for left < right {
		// 这就是在数组1 找边界; 如果是偶数边界=5 直接就是中间的; 如果是4 就是第三个
		i := left + (right-left+1)>>1
		// 确定了第一个数组的i, 那么第二个数组的j 一定会确定; len(left) = len(right) 这个条件的强约束
		j := l - i
		// 在 [0, m][0,m] 中找到 ii，使得：
		// B[j−1]≤A[i] 且 A[i−1]≤B[j]  <==> A[i−1]≤B[j]
		// [0, i-1]  [i+1, m]            [i-1, i] 这个就是我们当前比较的数 我们看数的边界;  在数学中处理边界问题是非常 常见且 重要的;
		if nums1[i-1] > nums2[j] {
			// 继续查找[0, ]
			right = i - 1
		} else {
			// 继续查找[,]
			left = i
		}
	}

	i, j := left, l-left

	// 处理边界问题
	if i != 0 {
		maxLeftNums1 = nums1[i-1]
	}

	if j != 0 {
		maxLeftNums2 = nums2[j-1]
	}

	if i != m {
		minRightNums1 = nums1[i]
	}

	if j != n {
		minRightNums2 = nums2[j]
	}

	// go 语言也就模型并发 和 一些语言天然支持的包管理等舒服了 但是 没有泛型的抽象 让代码实在难受 在有
	if (m+n)%2 == 1 {
		return float64(util.Max(maxLeftNums1, maxLeftNums2))
	} else {
		return (float64(util.Max(maxLeftNums1, maxLeftNums2)) + float64(util.Max(minRightNums1, minRightNums2))) / 2
	}
}

// 上面这个算法的分析过程真的非常有趣了
// A[0] A[1] ... A[i-1] | A[i] ... A[m-1]
// B[0] B[1] ... B[j-1] B[j] | ... B[n-1]

// 我们假设 m <= n;
// m 为偶数：  len(left) = len(right);  Max(Left) <= Min(Right);   		median = (Max(Left)+Min(Right)) >> 1;
// n 为奇数：  len(left) = len(right) + 1;  Max(Left) <= Min(Right);     median = Max(Left)

// 关键的分析过程 对于整体来说 m + n;
// 如果 m + n == even;
// 如果 m + n == odd;

// SearchInsert 搜索插入的位置 如果有就返回索引 如果没有 就返回应该插入的位置
// leetcode35 搜索插入的位置
func SearchInsert(nums []int, target int) int {
	var (
		left  = 0
		right = len(nums) - 1
	)

	for left <= right {
		mid := left + (right-left)>>1
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return left
}

// MaxArea 最大的面积
// leetcode11 盛最多水的容器
// area = (r-l)Min(p[r], p[l]) 这个就是面积的计算公式
// 每次查找必然 r-l 就是 -- 过程, min(x, y) 这个尽可能的大
func MaxArea(height []int) int {
	var (
		res   = 0
		left  = 0
		right = len(height) - 1
	)

	for left < right {
		h := 0
		area := 0
		// 左边低
		if height[left] < height[right] {
			h = height[left]
			left++
		} else {
			// 右边低
			h = height[right]
			right--
		}

		area = (right - left + 1) * h
		if res < area {
			res = area
		}
	}

	return res
}

// GenerateParenthesis 生成有效括号
// leetcode22 括号的生成
// 算法导论 深度优先遍历            DFS depth first search;    回溯+剪枝
// 所有的叶子节点就是解
func GenerateParenthesis(n int) []string {
	res := make([]string, 0)
	if n == 0 {
		return res
	}

	return dfs("", n, n, res)
}

func dfs(s string, l int, r int, res []string) []string {
	if l == 0 && r == 0 {
		return append(res, s)
	}

	// 分配右括号 就 必须有一个左括号存在
	if l > r {
		return res
	}

	if l > 0 {
		res = dfs(s+"(", l-1, r, res)
	}

	if r > 0 {
		res = dfs(s+")", l, r-1, res)
	}

	return res
}

// RemoveDuplicates 要求：空间复杂度 O(1) 时间复杂度 O(N)
// leetcode26 删除有序数组的重复项  要求原地删除  返回删除之后的数组的长度
// Level: easy
func RemoveDuplicates(nums []int) int {
	if len(nums) < 2 {
		return len(nums)
	}

	l := 0
	for r := 1; r < len(nums); r++ {
		// 如果这样 1 2 4 5 6 这样的不都要交换了 但是如果出现重复交换还是必须的;
		if nums[l] != nums[r] {
			l++
			if r != l {
				nums[l] = nums[r]
			}
		}
	}
	return l + 1
}

// RemoveElement 移除所有等于val元素
// leetcode27: 移除元素 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组  Level: easy
// 这个不是有序的
func RemoveElement(nums []int, val int) int {
	l := 0
	for r := 0; r < len(nums); r++ {
		if val != nums[r] {
			if r != l {
				nums[l] = nums[r]
			}
			l++
		}
	}

	return l
}
